题目分析
本题是一个大家都玩过的扑克游戏,小时候为了锻炼计算能力,家长和老师经常用扑克牌比赛,看谁能够使用四张牌迅速通过加减乘除得到24。
递归
这个题目其实也不难,我们模拟一下计算的过程即可,想得到24,肯定最后是由两个数字计算得到的。
题意中四个数字放在数组中,因此最后一步一定是两个数字放在数组中。
反过来说,倒数第二步一定是三个数字放在数组中,倒数第三步一定是四个数字放在数组中。
可以理解为F4 -> F3 -> F2 -> F1,其中F表示数组中的元素个数。F1如果唯一的一个数字等于24,表示最终答案正确。
所以本题可以使用递归的方式求解,由 $ F_n->F_{n-1} $ 的过程是从n个元素中选择两个进行加减乘除运算,因为运算有顺序,因此选择方式不是$ C_n^2$, 而是$ A_n^2 $,每一次选择有4种运算符,因此时间复杂度是 $ 4n^2 $。递归n次的结果,算法的**时间复杂度为O(4^n \times n^{2n}),空间复杂度为O(n)**。
因为这里n = 4固定,所以时间复杂度和空间复杂度都是$$ O(1) $$。
1 | class Solution { |
刷题总结
本题难度不大,能否想到使用递归的思路非常重要,此题还有一个陷阱是要注意浮点数计算时要考虑精度问题。